package Tree;

/**
 * ���ڵ��ʾ��
 *
 * @param <E>
 * @author wanyuxiang
 */
public class ParentTree<E> {
    private final static int treeSize = 100;// ���Ĵ�С
    private int nodeSize;// ����Ҷ�Ӹ���
    private Node<E>[] elementData;// ʹ���������ʽ�������������еĽڵ�

    public ParentTree() {
        nodeSize = 0;
        elementData = null;
    }

    // ���������
    @SuppressWarnings("unchecked")
    public ParentTree(E data) {
        elementData = new Node[treeSize];
        elementData[0] = new Node<E>(data, null, 0);
        nodeSize++;
    }

    @SuppressWarnings({"rawtypes", "unchecked"})
    public static void main(String[] args) {
        ParentTree<String> tree = new ParentTree("001");
        Node root = tree.elementData[0];
        tree.add("101", root, 1);
        tree.add("102", root, 1);
        tree.add("103", root, 1);
        tree.add("201", tree.get("101"), 2);
        tree.add("301", tree.get("201"), 3);

        System.out.println(tree);
        System.out.println(tree.deep());
    }

    //�������
    public int deep() {
        int max = 0;
        for (int i = 0; i < nodeSize; i++) {
            if (elementData[i].deep > max) {
                max = elementData[i].deep;
            }
        }
        return max;
    }

    public void add(E data, Node<E> parent, int deep) {
        if (nodeSize + 1 > treeSize) {
            throw new IndexOutOfBoundsException("�������Ĵ�С");
        }

        int newDeep = 0;

        for (int i = 0; i < nodeSize; i++) {
            if (parent == elementData[i]) {
                newDeep = elementData[i].deep;
                break;
            }
        }

        if (deep != newDeep + 1) {
            System.out.println("��ȴ���");
            return;
        }

        for (int i = 0; i < treeSize; i++) {
            if (elementData[i] == null) {
                elementData[i] = new Node<E>(data, parent, newDeep + 1);
                nodeSize++;
                return;
            }

        }
    }

    //���ݽڵ��ֵ�õ���Ӧ�ڵ�
    public Node<E> get(E value) {
        for (int i = 0; i < nodeSize; i++) {
            if (value == elementData[i].data) {
                return elementData[i];
            }
        }
        return null;
    }

    @Override
    public String toString() {
        StringBuffer sb = new StringBuffer();
        sb.append("[");
        for (int i = 0; i < nodeSize; i++) {
            sb.append(elementData[i].data + ",");
        }
        sb.append("]");
        sb.delete(sb.length() - 2, sb.length() - 1);
        return sb.toString();
    }

    public static class Node<T> {
        private T data;// �ڵ�����
        private Node<T> parent;// ���ڵ�
        private int deep;// ���

        public Node(T data, Node<T> parent, int deep) {
            super();
            this.data = data;
            this.parent = parent;
            this.deep = deep;
        }

        public String toString() {
            return "[���ݣ�" + data + ",���ڵ�:" + parent + ",��ȣ�" + deep + "]";
        }
    }

}